package control.util.bfs
{
	import control.manager.MapManager;
	
	import data.ExitsData;
	import data.MapData;
	
	import flash.utils.getTimer;

	/**
	 * 广度优先搜索法 
	 * @author Leo
	 * 
	 */	
	public class BFS
	{
		private static var _I :BFS = null;
		
		public var bfsNodesList :Array;
		
		private var openList :Array;
		private var closeList :Array;
		public function BFS(prv :PrivateClass)
		{
			
		}
		/**
		 * 初始化节点
		 */		
		private function initNotes():void
		{
			bfsNodesList = [];
			var mapDataList :Vector.<MapData> = MapManager.instance.mapDataList;
			for each(var mapData :MapData in mapDataList)
			{
				var bfsNode :BFSNode = new BFSNode();
				bfsNode.mapID = mapData.mapID;
				bfsNode.neighbours = findNeighbours(mapData);
				this.bfsNodesList.push(bfsNode);
				
			}
			
//			var startNode :BFSNode = bfsNodesList[0];
//			var endNode :BFSNode = bfsNodesList[1];
//			findPath(startNode,endNode);
		}
		/**
		 * 找到所有邻居节点 
		 * @param mapData
		 * @return 
		 * 
		 */		
		private function findNeighbours(mapData :MapData):Array
		{
			var result :Array = [];
			var node :BFSNode;
			for each(var exit :ExitsData in mapData.exitsDataList)
			{
				node = new BFSNode();
				node.mapID = exit.nextMapID;
				result.push(node);
			}
			return result;
		}
		
		public function findPath(start :int,end :int):Array
		{
			closeList  = [];
			openList  = [];
			initNotes();
			var startNode :BFSNode = findNode(start);
			var endNode :BFSNode = findNode(end);
			
			openList.push(startNode);
			startNode.parent = null;
			
			while(openList.length > 0)
			{
				var node :BFSNode = openList.shift();
				if(node.mapID == endNode.mapID)
				{
					//找到路径
					return createPath(startNode,endNode);
				}else
				{
					closeList.push(node);
					
					for each(var neighborNode :BFSNode in node.neighbours)
					{
						if(!isHaveInClose(neighborNode) &&
							!isHaveInOpen(neighborNode))
						{
							var n :BFSNode = findNode(neighborNode.mapID);
							n.parent = node;
							openList.push(n);
						}
					}
				}
			}
			
			return null;
		}
		/**
		 * 检查节点是否在关闭列表中 
		 * @param neighborNode
		 * @return 
		 * 
		 */		
		private function isHaveInClose(neighborNode :BFSNode):Boolean
		{
			for each(var node :BFSNode in this.closeList)
			{
				if(node.mapID == neighborNode.mapID)
				{
					return true;
				}
			}
			
			return false;
		}
		/**
		 * 检查节点是否在开放列表中 
		 * @param neighborNode
		 * @return 
		 * 
		 */		
		private function isHaveInOpen(neighborNode :BFSNode):Boolean
		{
			for each(var node :BFSNode in this.openList)
			{
				if(node.mapID == neighborNode.mapID)
				{
					return true;
				}
			}
			
			return false;
		}
		/**
		 * 寻找相应的地图节点 
		 * @param mapID
		 * @return 
		 * 
		 */		
		private function findNode(mapID :int):BFSNode
		{
			for each(var node :BFSNode in this.bfsNodesList)
			{
				if(node.mapID == mapID)
				{
					return node;
				}
			}
			
			return null;
		}
		
		/**
		 * 创建路径 
		 * @param startNode
		 * @param endNode
		 * 
		 */		
		private function createPath(startNode :BFSNode, endNode :BFSNode):Array
		{
			var path :Array  = [];
			while(endNode.parent != null)
			{
				path.push(endNode);
				endNode = endNode.parent;
			}
			path.push(startNode);
			
			path.reverse();
			
			var exitsList :Array = MapManager.instance.allExitDataList;
			var i :int = 0;
			var result :Array = [];
			for each(var node :BFSNode in path)
			{
				i++;
				if(i <= path.length - 1)
				{
					var next :BFSNode = path[i];
					for each(var exitData :ExitsData in exitsList)
					{
						if(exitData.nextMapID == next.mapID && exitData.curMapID == node.mapID)
						{
							result.push(exitData);
						}
					}
				}
			}
			
			return result;
			
		}

		public static function get I():BFS
		{
			if(_I == null)
			{
				_I = new BFS(new PrivateClass());
			}
			return _I;
		}

	}
}

class PrivateClass{}